package _18_剑指OfferII;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

public class _038_剑指OfferII每日温度 {

    public static void main(String[] args) {
        _038_剑指OfferII每日温度 v = new _038_剑指OfferII每日温度();

        int[] ins = {73, 74, 75, 71, 69, 72, 76, 73};
        System.out.println(Arrays.toString(v.dailyTemperatures(ins)));
    }

    // 贪心思想，从后往前遍历
    public int[] dailyTemperatures(int[] temperatures) {
        int len = temperatures.length;
        int[] ans = new int[temperatures.length];

        for (int i = len - 2; i >= 0; --i) {
            int position = i + 1;
            while (temperatures[position] <= temperatures[i]) {
                if (ans[position] == 0) {
                    position = i;
                    break;
                } else {
                    position += ans[position];
                }
            }
            ans[i] = position - i;
        }
        return ans;
    }

    // 单调栈  正向遍历
    public int[] dailyTemperatures2(int[] temperatures) {
        int len = temperatures.length;
        // 从后往前遍历
        Deque<Integer> maxStack = new LinkedList<>();
        int[] results = new int[len];
        for (int i = 0; i < len; i++) {
            while (!maxStack.isEmpty() && temperatures[i] > temperatures[maxStack.peek()]) {
                int preIndex = maxStack.pop();
                results[preIndex] = i - preIndex;
            }
            maxStack.push(i);
        }
        return results;
    }


    // 单调栈解法, 反向遍历
    public int[] dailyTemperatures1(int[] temperatures) {
        int len = temperatures.length;
        // 从后往前遍历
        Stack<Integer> maxStack = new Stack<>();
        int[] results = new int[len];
        for (int i = len - 1; i >= 0; --i) {
            while (!maxStack.isEmpty() && temperatures[maxStack.peek()] <= temperatures[i]) {
                maxStack.pop();
            }
            results[i] = maxStack.isEmpty() ? 0 : maxStack.peek() - i;
            maxStack.push(i);
        }
        return results;
    }

}
